Diffie-Hellman key agreement provided the first practical solution to the key distribution problem, in cryptographic systems. The key agreement protocol allows two parties never having met in advance or sharing key material to establish a shared secret by exchanging messages over an open (unsecured) channel. The security rests on the intractability of computing discrete logarithms or in factoring large integers.
With the advent of the Internet and such like, the requirement for large-scale distribution of public keys and public key certificates is becoming increasingly important to enable systems like Diffie-Hellman key agreement.
A number of vehicles are known by which public keys may be stored, distributed or forwarded over unsecured media without danger of undetectable manipulation. These vehicles include public-key certificates, identity-based systems, and implicit certificates. The objective of each vehicle is to make one party's public key available to others such that its authenticity and validity are verifiable.
A public-key certificate is a data structure consisting of a data part and a signature part. The data part contains cleartext data including as a minimum, a public key and a string identifying the party to be associated therewith. The signature part consists of the digital signature of a certification authority (CA) over the data part, effectively the encryption of the data with the CA's private key so it may be recovered with his public key, thereby binding the entities identity to the specified public key. The CA is a trusted third party whose signature on the certificate vouches for the authenticity of the public key bound to the subject entity.
Identity-based systems (ID-based system) resemble ordinary public-key systems, involving a private transformation and a public transformation, but parties do not have explicit public keys as before. Instead, the public key is effectively replaced by a party's publicly available identity information (e.g. name or network address). Any publicly available information, which uniquely identifies the party and can be undeniably associated with the party, may serve as identity information. Here a trusted CA is required to furnish each party with the private key corresponding to their public key.
An alternate approach to distributing public keys involves implicitly certified public keys. Here explicit user public keys exist, but they are to be reconstructed by the recipient rather than transported by explicitly signed public-key certificates as in certificate based systems. Thus implicitly certified public keys may be used as an alternative means for distributing public keys (e.g. Diffie-Hellman keys).
With a conventional certificate, the authenticity of the information must be verified to ensure that the sender and the sender's public key are bound to one another. With an implicit certification it is simply necessary to verify the sender's signature of the message using the implicit certificate. The primary advantage of implicit certificates is the computationally expense explicit certificate verification is not required as it is in certification schemes. Further, unconditionally trusted CAs are not required as they are in ID-based schemes.
An example of an implicitly certified public key mechanism is known as Gunther's implicitly-certified public key method. In this method:                1. A trusted server T selects an appropriate fixed public prime p and generator α of Z*p. T selects a random integer t, with 1≦t≦p−2 and gcd(t,p−1)=1, as its private key, and publishes its public key u=αt mod p, along with α, p.        2. T assigns to each party A a unique name or identifying string IA and a random integer kA with gcd(kA,p−1)=1. T then computes PA=αkA mod p. PA is A's key reconstruction public data, allowing other parties to compute (PA)a below.        3. Using a suitable hash function h, T solves the following equation for a:H(IA)≡t·PA+kAa(mod p−1)        4. T securely transmits to A the pair (r,s)=(PA,a), which is T's ElGamal signature on IA. (a is A's private key for a Diffie-Hellman key-agreement)        5. Any other party can then reconstruct A's Diffie-Hellman public key PAa entirely from publicly available information (α, IA, u, PA, p) by computing:PAa≡αH(IA)u−PA mod p         
Thus signing an implicit certificate needs one exponentiation operation, but reconstructing the ID-based implicitly-verifiable public key needs two exponentiations.
It is known that exponentiation in the group Z*p and its analog scalar multiplication of a point in E(Fq) is computationally intensive. An RSA scheme is extremely slow requiring successive squaring and multiplication operations. Elliptic curve (EC) cryptosystems are not only more robust but also more efficient by using doubling and adding operations. However, despite the resounding efficiency of EC systems over RSA type systems the computational requirement is still a problem particularly for computing devices having limited computing power such as “smart cards”, pagers and such like.
Significant improvements have been made in the efficacy of certification protocols by adopting the protocols set out in Canadian patent application 2,232,936. In this arrangement, an implicitly-certified public key is provided by cooperation between a certifying authority, CA, and a correspondent A.
For each correspondent A, the CA selects a unique identity IA distinguishing the entity A. The CA generates public data γA for reconstruction of a public key of correspondent A by mathematically combining a private key of the trusted party CA and a generator created by the CA with a private value of the correspondent A. The values are combined in a mathematically secure way such that the pair (IA, γA) serves as correspondent A's implicit certificate. The CA combines the implicit certificate information (IA, γA) in accordance with a mathematical function F(γA, IA) to derive an entity information f. A private key α of the correspondent A is generated from f and the private value of the correspondent A. The correspondent A's public key may be reconstructed from the public information, the generator γA and the identity IA relatively efficiently.
Certificates, implicit certificates, and ID-based systems provide assurance of the authenticity of public keys. However, it is frequently necessary to verify the status of the public key to ensure it has not been revoked by the CA.
Several solutions are known to this revocation problem, the most common being the use of certificate revocation lists (CRLs). Each CA maintains a CRL which contains the serial number of revoked certificates and is signed by the CA using its private key. When a recipient receives a message that has been secured with a certificate, the recipient will recover the serial number, and check the CRL.
Typically, therefore, the correspondent A will sign a message m with a private key, α, and forward it together with a certificate from the CA that binds the sender A and the public key αP. The recipient B checks the certificate and verifies the signature on the message m. The correspondent B will then ask the CA whether the certificate is valid and receives a message signed by the CA confirming the status of the certificate at a particular time. The correspondent B will then verify the signature on the CA's message and proceed accordingly to accept or reject the message sent by correspondent A.
During this process it is necessary for correspondent A to perform one signature, for the CA to perform one signature, and for the recipient B to verify three signatures.
CAs may also issue authorization or attributable certificates in addition to public-key certificates. In this case the certificate issued by the CA to the correspondent A has a certain expiry or has details such as a credit limit or access rights to certain programs.
However with each arrangement, verification of the certificates is necessary as the information contained in the certificate may change periodically, even within the life of the certificate.
Furthermore, a correspondent may wish to be recertified. This is particularly true if the correspondent has reason to believe that its implicit public key has been compromised. However, recertification is a costly process that requires the correspondent to regenerate its private key, securely communicate its private key with the CA, and regenerate the data for constructing and reconstructing the implicit public key.
Accordingly, there is a need for a technique that simplifies the verification and recertification of certificates issued by a certifying authority and it is an object of the present invention to provide a technique that obviates or mitigates the above disadvantages.